A temporary data saving area reserved in an information device or a communication device for queuing data therein is generally configured to fetch or add data from or to the first or last element, as found in data structures such as FIFO (First-In First-Out) or FILO (First-In Last-Out).
On the other hand, in a packet scheduling mechanism implemented in a communication device having a multiplexing function with the intention to accomplish both suppressed delays and optimized load distribution, data is input/output in an ordered relationship other than FIFO and FILO. Here, a manipulation is required to fetch, from a temporary data saving area, data shifted from the head of a queue by an offset amount of data size which is determined based on the congestion condition of each path. This technique has been proposed by the present applicant (Patent Document 1). A queue in Patent Document 1 must be implemented such that data can be fetched or added from or to any element even other than the first and last ones. Further, a scheme is desired for enabling a high-speed data access using an offset amount of data size from the head as a key. The realization of such a scheme requires data management which allows the key to take an arbitrary possible value as an offset, and enables high-speed data access even if the relationship between the key and data dynamically varies in association with deletion or addition of data.
A known scheme for managing ordered data in which any arbitrary element can be accessible involves a data structure which is configured in the form of a list or array. Out of these structures, in the array structure, a value which can be taken as a key is limited within a range in which identification numbers (indexes) are defined for array elements. Since this range is determined at a stage where a memory is reserved for the array structure, the range of the key is limited by the size of the array structure itself. On the other hand, in the list structure, the value of a key is not limited to the size of a list itself. However, in the list structure, when access is made to data corresponding to an arbitrary key, the key must be searched for on the list. An expected value for this search time is proportional to the number of elements, for example, in a linear search, and proportional to a logarithm of the number of elements in base 2 in a faster two-branch search. This gives rise to a problem in which a larger number of elements results in a longer time required for accessing, as compared with the array structure.
Existing techniques for searching for a corresponding element from a key at high speeds include a hash method, a triple array method (Non-Patent Document 1), and the like. However, these techniques cannot be readily applied, if they employ a key which exhibits dynamical changes due to deletion and insertion of an element, such as a total value or the like of metadata representative of an attribute of a data body (the size of the data body, the number of dropped bits, and the like) from the first data thereof, because of the difficulties in following corresponding changes in data and key, as described, for example, in Patent Document 1.
Also, for correctly maintaining the relationship between a dynamically changing key and elements at all times in a list structure, manipulations such as deletion, insertion, and the like of data must be followed by again setting keys for all elements which have to be updated due to these manipulations. For example, when a key is chosen to be a total value of metadata from the first element, deletion of certain data results in a change in the total value of metadata of all elements subsequent to that data, so that keys must be set again for all elements from the deleted element to the last element. When a larger number of elements must be set again, a longer time is needed to perform processing for again setting the keys.
As described above, the array structure and hash method, which provide fast accesses, are not suited to the management of ordered data which can take a key of an arbitrary value, where a key value for data intended for a manipulation or other data dynamically changes in the event of manipulations such as deletion and change of certain data, addition of new data, and the like. The list structure, on the other hand, has a problem in that excessive time is needed to access and manipulate data.
Patent Document 1: International Publication No. 2007/111331 Pamphlet
Non-Patent Document 1: Iriguchi, Tsuda, Shishibori, Aoe, “Efficient Storage Search Method for Graph Structure,” Transactions of the Institute of Electronics, Information and Communication Engineers D-1, Vol. J79-D-1, No. 8, pp. 502-510 (1996).